Dijkstra's Link State Algorithm

Tags: #◇CSNETWK #◇Computer Science #◇Computer Networks #◇Networking Protocols #◇Graph Theory Basics

---

◇Overview

Dijkstra's Algorithm is a "Link State" algorithm, meaning every router has a complete map of the network (the global topology) and identical link c...

◇Key Concepts

Source Node Goal Link Costs Distance Predecessor (p)

◇Details / Theory

◇1. Concept Overview: Link State (LS)

Definition

Dijkstra's Algorithm is a "Link State" algorithm, meaning every router has a complete map of the network (the global topology) and identical link cost information. It computes the least-cost path from a single source node to all other nodes in the network.

The Logic (Iterative)

1. Initialization: The router knows the cost to its direct neighbors. All non-neighbors are set to infinity ($\infty$).
2. Selection: Pick the unvisited node with the smallest tentative distance.
3. Relaxation: Check if going through this new node is cheaper than the current known path to its neighbors.
   Formula: $D(v) = \min(D(v), D(u) + c(u,v))$

◇2. The Network Topology

Dijkstra Step-by-Step Edge Relaxation Execution Loop

Resulting Shortest Path Tree (SPT) Rooted at Router U

Scenario Link Costs Summary:

• Direct Links from U: u-v = 6, u-x = 7, u-w = 9
• Cross-Domain Links: v-w = 8, v-x = 7, x-w = 5, x-y = 4
• Egress Links to Z: w-z = 5, y-z = 8

◇3. Problem Analysis

Question 1

What is the shortest distance to node x and what node is its predecessor? Write your answer as n,p

Analytical Breakdown:

1. Direct Path Check: U connects directly to X with a cost of 7.

2. Alternative Path Check: Can we beat 7?
   Path U $\rightarrow$ V $\rightarrow$ X? (Cost: $6 + 7 = 13$). No.
   Path U $\rightarrow$ V $\rightarrow$ W $\rightarrow$ X? (Cost: $6 + 8 + 5 = 19$). No.

3. Conclusion: The direct link is the optimal path.
   Distance: 7
   Predecessor (p): The node immediately before X is u.

Correct Answer: 7,u

Question 2

What is the shortest distance to node v and what node is its predecessor? Write your answer as n,p

Analytical Breakdown:

1. Direct Path Check: U connects directly to V with a cost of 6.

2. Alternative Path Check: Can we beat 6?
   Any other path (e.g., through X) would start with a cost of 7 (U $\rightarrow$ X), which is already higher than 6.

3. Conclusion: The direct link is the optimal path.
   Distance: 6
   Predecessor (p): The node immediately before V is u.

Correct Answer: 6,u

Question 3

What is the shortest distance to node z and what node is its predecessor? Write your answer as n,p

Analytical Breakdown:

This requires a multi-step search (Dijkstra's Loop).

1. Step 0 (Start): U is at 0.

2. Step 1 (Neighbors):
   To V: 6 (via U)
   To X: 7 (via U)
   To W: 9 (via U - Note: Diagram shows a curved link u-w with cost 9)

3. Step 2 (Expand V): V is cheapest (6).
   V $\rightarrow$ W: Cost is $6 + 8 = 14$. (Direct path 9 is better).

4. Step 3 (Expand X): X is next cheapest (7).
   X $\rightarrow$ W: Cost is $7 + 5 = 12$. (Old cost 9 is better).
   X $\rightarrow$ Y: Cost is $7 + 4 = 11$.

5. Step 4 (Expand W): W is next cheapest (9, via U).
   W $\rightarrow$ Z: Cost is $9 + 5 = 14$.

6. Step 5 (Expand Y): Y is next cheapest (11, via X).
   Y $\rightarrow$ Z: Cost is $11 + 8 = 19$. (Old cost 14 is better).

7. Conclusion: The cheapest path to Z comes from W.
   Total Cost: 14
   Predecessor: w

Correct Answer: 14,w

◇Summary of Logic (Cheat Sheet)

Algorithm Tip: Always explore the node with the lowest current cost first.

◇Common Pitfalls

Not always expanding the cheapest unvisited node next — Dijkstra is a greedy algorithm. Forgetting to update (relax) neighbors when a cheaper path is found through the newly expanded node. Assuming the algorithm works with negative edge weights — it does not; use Bellman-Ford instead.

◇Summary

TL;DR — Dijkstra’s algorithm computes shortest paths from a source by greedily expanding the lowest-cost unvisited node and relaxing its neighbors. It requires non-negative edge weights and runs in $O(n^2)$ or $O(n \log n)$ with a priority queue.

◇Links

Related: - ◇Pasted image 20251121093234.png Source / Reference:

◇References & Navigation

• Previous Topic: ◇Longest Prefix Matching
• Next Topic: ◇Dijkstra's Algorithm (Advanced)
• Related Notes: ◇Distance-Vector Routing and RIP, ◇Link-State Routing and OSPF